1. Field of the Invention
The present invention is directed to a highly-adaptive, loop-free, distributed routing algorithm which does not require synchronized clocks, for use in dynamic networks. The invention utilizes one of a family of algorithms which is known as a xe2x80x9clink reversalxe2x80x9d algorithm. The invention structures reactions as a temporally-ordered sequence of diffusing computations, with each computation including a sequence of directed link reversals. The invention is well suited for use in large, dynamic, bandwidth constrained networks. In such networks, rapid route maintenance with a minimum of communication overhead provides higher performance.
2. Description of the Related Art
Traditionally, practical datagram routing algorithms are designed for operation in static or quasi-static networks with hardwired links. In such networks bandwidth is relatively abundant, and the protocol design goals involve minimization of router state (to permit scalability) and rapid reaction to topological changes when they occur (to ensure good data routing performance). In other words, limiting protocol storage and time complexity are the primary design goals.
Distance-vector routing algorithms based on the distributed BellmannFord (BF) computation, such as the Routing Information Protocol (RIP) were among the earliest approaches. However, these approaches suffered from the well-known xe2x80x9ccounting-to-infinityxe2x80x9d problem that affected the time complexity (i.e., convergence times) of these protocols. There has been a large amount of theoretical and practical work seeking to remedy this problem and improve the performance of distance-vector approaches. The development of link state routing algorithms provided an alternative approach, in which the entire network topology is distributed to all nodes, allowing each router to independently compute paths to every destination. However, nearly all of this work continued in the direction started by the BF work and focused on the problem of xe2x80x9cshortest-pathxe2x80x9d routing. Shortest path routing techniques seek to route traffic over the xe2x80x9cleast costxe2x80x9d path to the destination (often times the shortest path measured in hop count), an approach that optimal routing theory indicates is favorable during periods of light traffic. One aspect inherent in this work is that supporting a shortest-path computation requires a certain amount of communication complexity within the routing protocol. This, in turn, requires that sufficient bandwidth be available in the network to enable the computation while still leaving enough bandwidth for actual data routing.
The invention considers the problem of routing in a dynamic network. An example of such a network is a mobile, multi-hop, wireless network which can be envisioned as a collection of routers (equipped with wireless receiver/transmitters) that are free to move about arbitrarily. The status of the communication links between the routers, at any given time, is a function of their positions, transmission power levels, antenna patterns, co-channel interference levels, and other time-varying factors. Thus, the mobility of the routers and variability of other connectivity factors result in a network with a potentially rapidly and unpredictably changing topology. Congested links are also an expected characteristic of such a network, as wireless links inherently have significantly lower capacity than their hardwired counterparts and are therefore more prone to congestion. The highly dynamic and bandwidth constrained nature of mobile networks most dramatically alters the trade-offs to be made in protocol design. Thus, it is communication complexity, not storage complexity, that is the greater determinant of protocol scalability in these networks. The combination of network size, topology dynamics and available bandwidth determines when approaches that do not perform shortest-path routing may be more desirable.
One embodiment of a temporally ordered routing algorithm, which is described in U.S. patent application Ser. No. 09/266,868, filed on Mar. 12, 1999, requires that nodes have clocks which are synchronized with each other in order to perform error-free routing. Dynamic, mobile networks such as those in which this algorithm is used may lose clock synchronization in one or more nodes. A routing method which would provide error free routing in the absence of synchronized clocks would be very useful. Such a method has been developed and is disclosed herein.
A routing algorithm which is well-suited for operation in a relatively dynamic or bandwidth-constrained networking environment, for example a mobile wireless networking environment, should therefore possess the following attributes:
Executes distributedly
Provides loop-free routes
Provides multiple routes (to alleviate congestion)
Establishes routes quickly (so they may be used before the topology changes)
Minimizes communication overhead by localizing algorithmic reaction to topological changes when possible (to conserve available bandwidth and increase scalability)
Based on these attributes, the inventors have developed a method referred to as the Temporally Ordered Routing Algorithm (TORA) which is a new routing method that is tailored for operation in a highly-dynamic networking environment, such as a mobile network. TORA""s design is based largely on the notion that high reactivity (i.e., low time complexity) and bandwidth conservation (i.e., low communication complexity) are of greater importance than routing optimality (i.e., determination of the shortest-path). A key concept in its design is an attempt to decouple (to the greatest extent possible) the generation of potentially far-reaching control message propagation from the dynamics of the network topology. The xe2x80x9cscopexe2x80x9d of control messaging following topological changes is typically localized to a very small set of nodes near the change without having to resort to a dynamic, hierarchical routing solution with its attendant complexity. A possible enhancement to the protocol (to be discussed later) would be to embed farther-reaching control message propagation into the protocol as a secondary mechanism. This propagation would occur periodically at a very low rate, independent of the network topology dynamics, and would be employed as a means of infrequent route optimization and soft-state route verification.
TORA is distributed, in that nodes need only maintain information about adjacent nodes (i.e., one-hop knowledge). Like a distance-vector routing algorithm, TORA maintains state on a per-destination basis. This property is exploited in the design by establishing routing for each given destination on-demand, since it may not be necessary (nor desirable) to maintain routes between every source/destination pair at all times. The overhead expended to establish a route between a given source/destination pair will be wasted if the source does not require the route prior to its invalidation due to topological changes. Thus, TORA is xe2x80x9csource initiatedxe2x80x9d and creates a set of routes to a given destination only when there is message traffic for that destination. It guarantees all routes are loop-free, and typically provides multiple routes for any source/destination pair that requires a route. Since having a single route is sufficient, many topological changes require no algorithmic reaction. Following topological changes that do require reaction, the protocol quickly re-establishes valid routes. This ability to initiate and react infrequently serves to further minimize communication overhead. Finally, in the event of a network partition, the protocol detects the partition and erases all invalid routes.
While not described here, TORA may be easily modified to run in a traditional pro-active, xe2x80x9cdestination-initiatedxe2x80x9d mode where all nodes actively maintain routing to a given destination (presumably a xe2x80x9cfrequent destinationxe2x80x9d for many nodes), thereby removing the need for source-initiated, on-demand route creation.
This original TORA embodiment, which is also described in U.S. patent application Ser. No. 09/266,868, requires that all nodes have synchronized clocks.
In a new embodiment of the TORA routing algorithm disclosed herein, the TORA algorithm does not require synchronized clocks in order to perform error free routing to a given destination.